package 算法.leetcode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author:谢君臣
 * @Date:2021/5/10-10:08
 * @version:1.0
 * @function:
 */
public class lc872 {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> list1 = DFS(root1);
        return checkList(list1,root2);
    }

    private boolean checkList(List<Integer> list1, TreeNode root) {
        int i = 0;
        Stack<TreeNode> stack = new Stack<>();
        while (root!=null||!stack.isEmpty()){
            while (root!=null){
                stack.push(root);
                root = root.left;
            }
            if (!stack.isEmpty()){
                root = stack.pop();
                if (root.left==root.right)
                {
                    if (i>=list1.size()||root.val != list1.get(i))
                        return false;
                    i++;
                }
                if (root.right!=null)root= root.right;
                else root = null;
            }
        }
        return i==list1.size();
    }

    List<Integer> DFS(TreeNode root){
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root!=null||!stack.isEmpty()){
            while (root!=null){
                stack.push(root);
                root = root.left;
            }
            if (!stack.isEmpty()){
                root = stack.pop();
                if (root.left==root.right)res.add(root.val);
                if (root.right!=null)root= root.right;
                else root = null;
            }
        }
        return res;
    }
}
